Адміністрація вирішила продати даний сайт. За детальною інформацією звертайтесь за адресою: rozrahu@gmail.com

Емуляція на ПЕОМ машин Тюрінга

Інформація про навчальний заклад

ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
Не вказано
Кафедра:
Не вказано

Інформація про роботу

Рік:
2005
Тип роботи:
Лабораторна робота
Предмет:
Теорiя алгоритмiв i математичнi основи представленння знань
Група:
КН

Частина тексту файла

Міністерство освіти та науки України Національний Університет “Львівська політехніка” Інститут комп´ютерних наук та інформаційних технологій Лабораторна робота №3 з курсу:“Теорія алгоритмів і математичні основи представлення знань” на тему :” Емуляція на ПЕОМ машин Тюрінга.” Мета лабораторної роботи - емуляцiя на ПЕОМ машин Тьюрінга і конструювання програм для них. I. ЗАГАЛЬНІ ПОЛОЖЕННЯ Для засвоєння поняття машин Тьюрінга і освоєння конструювання Т-машин необхідно в певній мірі автоматизувати тестування та відладку програм Т-машин (Т-програм). Для цього необхідно в данній лабораторній роботі емулювати на ПЕОМ машину Тьюрінга, яка б по заданій Т-програмі Пт і входу w імітувала обчислення функції F, що задається Пт. В основі алгоритмічної системи Тюрінга лежить поняття абстрактнго автомата - машини Тюрінга (Т-машини). В літературі наведено багато варіантів визначення Т-машини. Ми розглядатемемо найбільш поширений варіант цієї машини. Нехай задано вхідний алфавіт Eвх  2= 0 {a1,..,an}, внутрішній алфавіт Eвн  2= 0 {b1,..,br}, і E об’єднання алфавітів Eвх і Eвн, причому перетин Eвн і Eвх є пустою множиною. E будемо називати повним алфавітом. Елементи алфавітів називаються буквами або літерами. Через E* позначимо множину всіх слів в алфавіті E, включаючи пусте слово e, а, відповідно, через E*вх - множину всіх вхідних слів. Довільну скінченну підмножину Q  2= 0 {q0,q1,..,qm} деякої нескінченної множини Q^  2= 0 {..,q(-1),q0,..qm,..} будемо називати множиною міток, а її елементи - мітками. Будемо вважати, що перетин Q і E є пустою множиною. Командю Тюрінга (Т-командою ) називається вираз вигляду q d -> q'd'r (1) де q і q' - мітки із Q, d і d' - літери із E, а r приймає значення одного із трьох чисел : -1,0,+1. Пара qd із (1) називається Т-міткю. Програмою Тюрінга (Т-програмою) називається довільна скінченна сукупність Пт Т-команд U0 U1 (2) .. Um в якій різні команди мають різні Т-мітки. Машиною Тюрінга називається довільний набір Мт  2= 0 (Q,E,q^,#,Пт), де: Q - множина міток; E -об'єднання вхідного Eвх та внутрішнього Eвн алфавітів; q^ - виділений елемент із Q, який називається початковою міткою Мт; # - виділений елемент із Eвн; Пт - Т-програма. Коли команда q d -> q'd'r входить в програму Пт Т-машини Мт, тоді мітка q і Т-мітка (q d) називаються прміжковими мітками. Всі непроміжкові мітки і Т-мітки називаються кінцевими мітками Т-машини Мт. Станом Т-машини (Т-станом) називається довільна нескінченна в обидва боки послідовність t  2= 0 ...d(-2) d(-1) q d(0) d(1) d(2)... (4) де d(j) (j  2= 0...-2,-1,0,1,2,...) - літери із E, а q - мітка із Q. Для машини Мт Т-стан (4) називається : а) початковим, коли q  2= 0 q^ ; б) проміжковим, коли < q d(0) > - проміжкова Т-мітка; в) кінцевим, коли < q d(0) > - кінцева Т-мітка Мт. Множину всіх станів Т-машини Мт позначимо через Dм. Тепер визначимо функцію переходів Fт : Dм --> Dм.Коли Т-мітка <q d(0)> - кінцева в стані (4), то Fт(t)  2= 0 t.Нехай <q d(0)> - проміжова Т-мітка стану (4). Тоді в програмі Пт знайдеться одна і тільки одна команда вигляду q d(0) -> q'd'r. Під дією ціїє команди Т-стан t переходить в стан t'  2= 0 Fт(t). Залежно від r  2= 0 +1,0,-1 значення tr  2= 0 Fт(t) приймає вигляд : t+  2= 0 ...d(-2) d(-1) d' q' d(1) d(2)... t0  2= 0 ...d(-2) d(-1) q' d' d(1) d(2)... (5) t-  2= 0 ...d(-2) q' d(-1) d' d(1) d(2)... Із (5) випливає, що при r  2= 0 +1,0,-1 вираз "q d(0)" в стані (4),відповідно, замінюється на вирази " d' q' ", "q' d' " i " q' d(-1) d' " . Тепер опишемо, яким чином кожній Т-машині Мт можна співставити функцію f[Мт] : E*вх --> E*.Далі через /d/  2= 0 ...ddddd... будемо позначати нескінченну послідовність літери ...
Антиботан аватар за замовчуванням

01.01.1970 03:01

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини